package com.itheima.leetcode.od.b.dynamicprogramming;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.stream.Collectors;

/**
 * (A卷,100分)- 等和子数组最小和（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 给定一个数组nums，将元素分为若干个组，使得每组和相等，求出满足条件的所有分组中，组内元素和的最小值。
 * <p>
 * 输入描述
 * <p>
 * 第一行输入 m
 * 接着输入m个数，表示此数组nums
 * 数据范围：1<=m<=50, 1<=nums[i]<=50
 * <p>
 * 输出描述
 * <p>
 * 最小拆分数组和
 * <p>
 * 用例
 * <p>
 * 输入	7
 * <p>
 * 4 3 2 3 5 2 1
 * <p>
 * 输出	5
 * 说明
 * 可以等分的情况有：
 * <p>
 * 4 个子集（5），（1,4），（2,3），（2,3）
 * <p>
 * 2 个子集（5, 1, 4），（2,3, 2,3）
 * <p>
 * 但最小的为5。
 * <p>
 * 题目解析
 * <p>
 * 本题算是LeetCode - 698 划分为k个相等的子集_伏城之外的博客-CSDN博客
 * <p>
 * 的变种题，本题同样是要将数组划分为k个和相等的子集。
 * <p>
 * 本题要我们求解：最小拆分数组和，其实就是求解：最小子集和，其实就是求解，最大k值。因为k值越大，则对应的子集的和越小。
 * <p>
 * 这里k的求解很简单，首先，我们可以猜想下k的上限是多少？
 * <p>
 * 比如数组所有元素都相等，则k === m，即每个元素都能作为一个子集，因此我们可以让k从m开始尝试，如果不行，则k--，直到k=1。
 * <p>
 * 而验证nums是否可以划分为k层，其实就是判断nums是否可以划分为k个和相等的子集，这个判断逻辑可以复用LeetCode - 698 划分为k个相等的子集_伏城之外的博客-CSDN博客
 * <p>
 * 中的逻辑。
 */
public class MinimumSumOfEqualSumSubarrays {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();

        LinkedList<Integer> link = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            link.add(sc.nextInt());
        }*/

        String input = "4 3 2 3 5 2 1";
        LinkedList<Integer> link = Arrays.stream(input.split(" "))
                .map(Integer::parseInt)
                .collect(Collectors.toCollection(LinkedList::new));
        System.out.println(getResult(link, 7));
    }

    public static int getResult(LinkedList<Integer> link, int m) {
        int sum = link.stream().reduce(Integer::sum).orElse(0);
        int min = sum;

        MinimumSumOfEqualSumSubarraysLeetcode698 leetcode698 = new MinimumSumOfEqualSumSubarraysLeetcode698();
        while (m > 0) {
            if (leetcode698.canPartitionKSubsets(link.stream().mapToInt(Integer::intValue).toArray(), m)) {
                min = sum / m;
                return min;
            }
            m--;
        }
        return min;
    }
}